package com.example.demo.leetcode.zuocheng.btree;

import com.example.demo.leetcode.zuocheng.graph.Node;

/**
 * @author xujm
 * @version V2.4
 * @since 2.4.0 2021/8/28 14:16
 */
public class Tree_二叉树是否满的 {

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }

    public static class NodeInfo{
        int height;
        int nodes;

        public NodeInfo(int height, int nodes) {
            this.height = height;
            this.nodes = nodes;
        }

        public int getHeight() {
            return height;
        }

        public void setHeight(int height) {
            this.height = height;
        }

        public int getNodes() {
            return nodes;
        }

        public void setNodes(int nodes) {
            this.nodes = nodes;
        }
    }



    // 判断一个二叉树是否是满的
    // 求出二叉树的 高度 和 节点个数
    // 如果 2的高度次方-1 == 节点个数  则是满的
    public static boolean isFullFromTree(TreeNode root){

        NodeInfo process = process(root);
        return  (1<<process.height)-1 == process.nodes;

    }


    public static NodeInfo process(TreeNode root){
        if(root == null){
            return new NodeInfo(0,0);
        }
        NodeInfo rightNodeInfo = process(root.right);
        NodeInfo leftNodeInfo = process(root.left);
        int height = Math.max(rightNodeInfo.height,leftNodeInfo.height)+1;
        int nodes = rightNodeInfo.nodes + leftNodeInfo.nodes + 1;
        return new NodeInfo(height,nodes);
    }

    public static void main(String[] args) {
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(6);
        TreeNode treeNode7 = new TreeNode(7);
        treeNode1.left=treeNode2;treeNode1.right=treeNode3;
        treeNode2.left=treeNode4;treeNode2.right=treeNode5;
        treeNode3.left=treeNode6;treeNode3.right=treeNode7;

        System.out.println(isFullFromTree(treeNode1));
    }


}
